package 回溯;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/6/14 13:29
 */
public class lc2257统计网格图中没有被保卫的格子数 {
    public static int solution(int m,int n,int g[][],int w [][]) {
        int ans = 0;
        int res [][] = new int [m][n];
        for(int arr [] : w) {
            res[arr[0]][arr[1]] = -1;
        }
        for(int arr[] : g)
            dfs(m,n,res,arr[0],arr[1]);
//		for(int )
        return ans;
    }
    static void  dfs(int m,int n,int res[][],int x,int y) {
        for(int arr [] : dirs ) {
            int nx = x + arr[0];
            int ny = y + arr[1];
            if(nx < 0 || ny < 0 || nx >= m || ny >= n || res[nx][ny] == -1)
                continue;
            res[nx][ny] = 1;
            dfs(m,n,res,nx,ny);
            break;
        }
    }
    static void process(int m,int n,int x,int y,int dir[],int res[][]) {
//		if(res[x][y] )
        int nx = x + dir[0];
        int ny = y + dir[1];
        if(nx < 0 || ny < 0 || nx >= m || ny >= n || res[nx][ny] == -1)
            return ;
        process(m,n,nx,ny,dir,res);
    }
    /**
     * 30 ms 左右
     * TLE  还是 ac  就在
     * 	for(int arr[] : g)
     //  守卫 所在的 位置 直接默认 就是  能守卫 的
     res[arr[0]][arr[1]] = -2;
     这一段 代码 上面
     我感觉 这个 dfs 还是  可以 优化的
     */
    static int dirs[][] = {{1,0},{-1,0},{0,1},{0,-1}};
    static int solutionOne(int m,int n,int g[][],int w[][]) {
        int ans = 0;
        int res [][] = new int [m][n];
        // 先把 强 标为 -1
        for(int arr [] : w) {
            res[arr[0]][arr[1]] = -1;
        }
        for(int arr[] : g)
            //  守卫 所在的 位置 直接默认 就是  能守卫 的
            res[arr[0]][arr[1]] = -2;
        // 能 保卫 直接  赋值 为 1；
        for(int  i [] : g) {
            for(int dir[] : dirs) {
//				if(res[])
                dfsOne(m,n,res,i[0] + dir[0],i[1] + dir[1],dir);
            }
        }
        for(int arr [] : res) {
            for(int i : arr) {
                //  注意 墙体 是 不计算在内 的
                if(i == 0)
                    ans++;
            }
        }
        return ans;
    }
    static void dfsOne(int m,int n,int res[][],int x,int y,int dir[]) {
        /**
         * 只 做了 边界 判断  和 wall 体 判断
         * res[x][y] == -2
         * 直接  return 啥意思 就是
         * 当前的  guard1 在 某个  直线  方向 上 遇到了 另外 一个 guard2
         * 那 当前的 直线方向 就直接 交给    guard2 处理 就行 （这是 一个 小小的  剪枝 优化 ）
         */
        if(x < 0 || y < 0 || x >= m || y >= n || res[x][y] == -1 || res[x][y] == -2)
            return ;
//		return 0;
        res[x][y] = 1;
        dfsOne(m,n,res,x + dir[0],y + dir[1],dir);
    }




    /**
     * 17 ms 左右
     * @author I adore you
     *
     */

    public int countUnguarded(int m, int n, int[][] guards, int[][] walls) {
        int grid[][] = new int[m][n], count = 0;
        for (int[] guard : guards) {
            grid[guard[0]][guard[1]] = 2;
        }
        for (int[] wall : walls) {
            grid[wall[0]][wall[1]] = 2;
        }
        for (int[] guard : guards) {
            for (int i = guard[0] - 1; i >= 0 && grid[i][guard[1]] < 2; i--) {
                grid[i][guard[1]] = 1;
            }
            for (int i = guard[0] + 1; i < grid.length && grid[i][guard[1]] < 2; i++) {
                grid[i][guard[1]] = 1;
            }
            for (int i = guard[1] - 1; i >= 0 && grid[guard[0]][i] < 2; i--) {
                grid[guard[0]][i] = 1;
            }
            for (int i = guard[1] + 1; i < grid[0].length && grid[guard[0]][i] < 2; i++) {
                grid[guard[0]][i] = 1;
            }
        }
        for (int[] i : grid) {
            for (int j : i) {
                count += 1 - Math.min(1, j);
            }
        }
        return count;
    }

}
